package com.itheima.algorithm.recursion_single;

import java.util.Arrays;

/**
 * 递归冒泡排序
 * <ul>
 *     <li>将数组划分成两部分 [0 .. j] [j+1 .. a.length-1]</li>
 *     <li>左边 [0 .. j] 是未排序部分</li>
 *     <li>右边 [j+1 .. a.length-1] 是已排序部分</li>
 *     <li>未排序区间内, 相邻的两个元素比较, 如果前一个大于后一个, 则交换位置</li>
 * </ul>
 */
public class E04BubbleSort {

    public static void sort(int[] a) {
        bubble0(a, a.length - 1);
    }


    public static void main(String[] args) {
        int[] a = {6, 5, 4, 3, 2, 1};
        System.out.println(Arrays.toString(a));
        bubble0(a, a.length - 1);
        System.out.println(Arrays.toString(a));


//        int[] b = {11, 22, 33, 44, 55, 66};
//        System.out.println(Arrays.toString(b));
//        bubble1(b, b.length - 1);
//        System.out.println(Arrays.toString(b));
    }


    /**
     * <h3>递归函数 在范围 [0 .. right] 内冒泡最大元素到右侧</h3> 升序冒泡
     *
     * @param a     数组
     * @param right 0 ~ right 未排序的区域
     */

    private static void bubble0(int[] a, int right) {
        if (right <= 0) {
            return;
        }
        int x = 0;// 减小边界搜索范围
        //从0 ~ right-1 中找出最大元素，并放到 right 索引位置
        for (int i = 0; i < right; i++) {
            //如果index =i 的元素比 index = i + 1 的元素大，则交换位置
            if (a[i] > a[i + 1]) {
                //相邻交换
                int temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
                //一旦发生交换，则将x 置为当前索引
                x= i;
            }
        }
        bubble0(a, x);
    }

    /**
     * <h3>递归函数 在范围 [0 .. right] 内冒泡最大元素到右侧</h3> 降序冒泡
     *
     * @param a     数组
     * @param right 0 ~ right 未排序的区域
     */
    public static void bubble1(int[] a, int right) {
        if (right <= 0) {
            return;
        }
        int x = 0;// 减小边界搜索范围
        //从0 ~ right-1 中找出最大元素，并放到 0 索引位置
        for (int i = 0; i < right; i++) {
            //如果index =i 的元素比 index = i + 1 的元素小，则交换位置
            if (a[i] < a[i + 1]) {
                int temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
                //一旦发生交换，则将x 置为当前索引
                x= i;
            }
        }

        bubble1(a, x);

    }


}
